package SearchMethods;

public class InsertValue {
    public static void main(String[] args) {
        int[] arr=new int[]{1,2,3,4,5,6,7,8,9,15,27};
        int i = insertValueSearch(arr, 0, arr.length - 1, 6);
        System.out.println(i);
    }

    public static int insertValueSearch(int[] arr,int left, int right ,int target){

        System.out.println("插值查找次数~~~");
        //不能让mid 越界
        if (left>right||target<arr[0]||target>arr[arr.length-1]){
            return -1;
        }
        int mid=left+(right-left)*(target-arr[left])/(arr[right]-arr[left]);
        int midVal=arr[mid];
        if (target<midVal){
            System.out.println("左递归~~~");
            //向左递归
            return insertValueSearch(arr,left,mid,target);
        }else if ( target>midVal){
            System.out.println("右递归~~~");
            return insertValueSearch(arr,mid+1,right,target);
        }else {
            return mid;
        }
    }
}
